package com.zhugang.week13.linkedlist;

/**
 * @program algorithms
 * @description: getIntersectionNode
 * @author: chanzhugang
 * @create: 2022/10/27 21:18
 */
public class GetIntersectionNode {

    /**
     * 160 相交链表
     * https://leetcode.cn/problems/intersection-of-two-linked-lists/
     *
     * @param headA
     * @param headB
     * @return
     */
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        // 相交： 让长的链表先走｜lenA - lenB｜, 再两个链表一起走，只要不相等，一直next
        // 分别计算链表A、B长度
        ListNode pA = headA;
        int lenA = 0;
        while (pA != null) {
            lenA++;
            pA = pA.next;
        }

        ListNode pB = headB;
        int lenB = 0;
        while (pB != null) {
            lenB++;
            pB = pB.next;
        }

        // 找的链表先走 |lenA - lenB|
        ListNode qA = headA;
        ListNode qB = headB;
        if (lenA >= lenB) {
            for (int i = 0; i < lenA - lenB; i++) {
                qA = qA.next;
            }
        } else {
            for (int i = 0; i < lenB - lenA; i++) {
                qB = qB.next;
            }
        }

        // 一起走, 不相等一直next
        /*while (qA != null && qB != null && qA != qB) {
            qA = qA.next;
            qB = qB.next;
        }
        if (qA == null || qB == null) {
            return null;
        }*/
        while (qA != qB) {
            // 优化
            qA = qA.next;
            qB = qB.next;
        }
        return qA;
    }

    public class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
            next = null;
        }
    }
}
